1534. Divisibility
You are given a set of integers a1, a2,
..., an. Determine the
number of integers in the range from l to r (inclusive) that are
divisible by at least one number from this set.
Input. The input consists of multiple
test cases. The first line of each test case
contains two integers l (1 ≤ l ≤ 109) and r (1 ≤ r ≤ 109), defining the range boundaries. The second line contains the number of elements n (1 ≤ n ≤ 18) in the set and the set of integers a1, a2, ..., an.
Each integer in the set is between 1 and 109.
Output. For each test case, print a single line with the number of integers in the range [l, r] that are divisible by at least
one number from the set a1, a2,
..., an.
|
Sample
input |
Sample
output |
|
293 784 1 1 579000
987654 2 1 2 1 1000000000 2 2 3 |
492 408655 666666667 |
SOLUTION
combinatorics - inclusion-exclusion
principle
Algorithm analysis
Let a = { a1, a2,
..., an } be the set of numbers. Let numDivisible(l, r, a) be the amount of numbers
from l to r inclusively, that are divisible by at least one
of the numbers a1, a2, ..., an. Use the fact that
numDivisible(L,
R, a) = numDivisible(1, R, a) – numDivisible(1, L – 1, a).
The value numDivisible(1, n,
a) will be computed by means of a function f(n, a).
Consider the
process of computing the result
depending on the number of elements in the array a.
1. If a contains only one element, the answer is the value n / a[0] (rounding
to the nearest integer down).
2. Let a contains two elements. The answer will be less
than n / a[0] + n / a[1] because there
will be numbers divisible by a[0] and a[1] simultaneously. And in the sum these numbers will be counted twice. The amount of numbers
divisible by both a[0] and a[1] equals to n / LCM(a[0], a[1]). Thus, for two numbers
f(n, a)
= n / a[0] + n / a[1] –
n / LCM(a[0], a[1])
3. Let a contains three elements. Then according to inclusion -
exclusion principle
f(n, a)
= n / a[0] + n / a[1] + n
/ a[2] –
– n / LCM(a[0], a[1]) – n /
LCM(a[1], a[2]) – n / LCM(a[0], a[2]) +
n / LCM (a[0],
a[1], a[2])
Since by the
problem statement the array a
contains from 1 to 18 elements, it is possible to iterate over all subsets of
the set a in no more than 218
operations. Moreover, if the subset 
contains an odd number
of elements, then the value of n / LCM(
) should be added to the accumulated sum (answer), if it is
even, then subtract.
If, when
calculating LCM (
), the current value of LCM (
) becomes greater than n
for some j < k, then the process of computing LCM () can be completed, since then n / LCM() = 0.
Algorithm realization
Function f(n, a)
computes the
value of numDivisible(1, n, a). Function gcd computes the greatest
common divisor of two numbers.
int f(int N, int *a)
{
The answer is computed in the variable res.
int res = 0;
Iterate over all subsets of the set { a1, a2, ..., an }. The variable i contains the mask of a subset.
for(int i = 1; i <
(1<<n); i++)
{
In the variable lcm compute the LCM of the
subset specified by the mask i.
long long
lcm = 1;
In the variable bits
count the number of elements in the subset specified by the mask i (the number of bits equal to 1 in i).
int bits = 0;
for(int
j = 0; j < n; j++)
if (i & (1 << j))
{
bits++;
int temp = gcd(lcm,a[j]);
lcm = lcm / temp * a[j];
If the LCM of the subset becomes larger than N, then there is
no sence in further
computing. Anyway, the N / lcm value
is zero.
if (lcm > N) break;
}
Depending on the parity of the number of bits in the mask
(the number of elements in the current considered subset), add or subtract the
next term.
if (bits % 2) res += N / lcm; else res -= N / lcm;
}
return res;
}
The main part of
the program. Read the input
data.
while(scanf("%d %d",&l,&r)
== 2)
{
scanf("%d",&n);
for(i = 0; i < n; i++) scanf("%d",&a[i]);
Compute the required amount of numbers on a segment [l; r ].
res = f(r,a) - f(l - 1,a);
Print the answer.
printf("%d\n",res);
}